package com.TheEndWork;

import javax.swing.plaf.SliderUI;
import java.util.*;

/**
 * @authoer zsj
 * @date 2022/6/4 16:25
 */
public class 二分查找 {
    /**
     * leecode 704
     * 给定一个n个元素有序的（升序）整型数组nums 和一个目标值target ，写一个函数搜索nums中的 target，
     * 如果目标值存在返回下标，否则返回 -1。
     */
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] < target) {
                //如果目标值大于当前值，缩小区间为
                left = mid + 1;
            }
            if (nums[mid] > target) {
                //如果目标值小于当前值，缩小区间为
                right = mid - 1;
            }
        }
        return -1;
    }

    static int guess(int n) {
        int pick = 1;//最终数字
        if (n < pick) return 1;
        else if (n > pick) return -1;
        return 0;
    }

    /**
     * 猜数字游戏的规则如下：
     * 每轮游戏，我都会从1到n 随机选择一个数字。 请你猜选出的是哪个数字。
     * 如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
     * 你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，
     * 返回值一共有 3 种可能的情况（-1，1或 0）：
     * -1：我选出的数字比你猜的数字小 pick < num
     * 1：我选出的数字比你猜的数字大 pick > num
     * 0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num
     * 返回我选出的数字。
     */
    public int guessNumber(int n) {
        int left = 1;
        int right = n;
        int ans = 0;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (guess(mid) == 0) {
                ans = mid;
                break;
            }
            if (guess(mid) == -1) {
                //说明当前的值大于了目标值
                right = mid - 1;
            }
            if (guess(mid) == 1) {
                //说明当前的值小于了目标值
                left = mid + 1;
            }
        }
        return ans;
    }


    /**
     * 给你一个大小为m* n的矩阵mat，矩阵由若干军人和平民组成，分别用 1 和 0 表示。
     * 请你返回矩阵中战斗力最弱的k行的索引，按从最弱到最强排序。
     * 如果第i行的军人数量少于第j行，或者两行军人数量相同但 i 小于 j，那么我们认为第 i 行的战斗力比第 j 行弱。
     * 军人 总是 排在一行中的靠前位置，也就是说 1 总是出现在 0 之前。
     */
    public static int[] kWeakestRows(int[][] mat, int k) {
        int n = mat.length;
        int m = mat[0].length;
        //思路就是把每一行的军人数量记录出来，并且记录下标
        int[] ans = new int[k];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int count = 0;
            for (int j = 0; j < m; j++) {
                count += mat[i][j];
            }
            //求出当前行数的军人
            map.put(i, count);
        }
        List<Map.Entry<Integer, Integer>> list = new ArrayList<Map.Entry<Integer, Integer>>(map.entrySet());
        Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o1.getValue().compareTo(o2.getValue());
            }
        });
//        for (Map.Entry<Integer, Integer> integerIntegerEntry : list) {
//            System.out.println("行" + integerIntegerEntry.getKey());
//            System.out.println("军人数量" + integerIntegerEntry.getValue());
//        }
        for (int i = 0; i < k; i++) {
            ans[i] = list.get(i).getKey();
        }
        return ans;
    }


    /**
     * 给你一个整数数组arr，请你检查是否存在两个整数N 和 M，满足N是M的两倍（即，N = 2 * M）。
     * 更正式地，检查是否存在两个下标i 和 j 满足：
     */
    public static boolean checkIfExist(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                if (i == j) continue;
                if (arr[j] * 2 == arr[i]) return true;
            }
        }
        return false;
    }


    /**
     * 给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。
     */
    public static boolean judgeSquareSum(int c) {
        long l = 0;
        long r = (long) Math.sqrt(c);
        while (l <= r) {
            long sum = l * l + r * r;
            if (sum == c) return true;
            if (sum > c) r--;
            if (sum < c) l++;
        }
        return false;
    }

//    public static void main(String[] args) {
////        int[][] arr = {{1, 1, 0, 0, 0},
////                {1, 1, 1, 1, 0},
////                {1, 0, 0, 0, 0},
////                {1, 1, 0, 0, 0},
////                {1, 1, 1, 1, 1}};
////        kWeakestRows(arr, 3);
////        int[] arr = {-2, 0, 10, -19, 4, 6, -8};
////        checkIfExist(arr);
//        int[] a1 = {55,30,5,4,2};
//        int[] a2 = {100,20,10,10,5};
//        intersect(a1, a2);
//    }

    /**
     * 给你两个整数数组nums1 和 nums2 ，请你以数组形式返回两数组的交集。
     * 返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。
     * 可以不考虑输出结果的顺序。
     */
    public static int[] intersect(int[] nums1, int[] nums2) {
        //就返回两个数组中相同的字母
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        List<Integer> ans = new ArrayList<>();
        for (int i = 0, j = 0; i < nums1.length && j < nums2.length; ) {
            if (nums1[i] == nums2[j]) {
                //说明是交集
                ans.add(nums1[i]);
                //将两个下标都往后移
                i++;
                j++;
            } else if (nums1[i] > nums2[j]) {
                //如果数组1中的数字大于了数组2中的数字说明
                j++;
            } else {
                i++;
            }
        }
        int[] res = new int[ans.size()];
        int index = 0;
        for (int i : ans) {
            res[index++] = i;
        }
        return res;
    }

    public static void main(String[] args) {
        /*
        [30,29,19,5]
[25,25,25,25,25]
         */
        int[] a1 = {55,30,5,4,2};
        int[] a2 = {100,20,10,10,5};
        System.out.println(maxDistance(a1, a2));
    }
    /**
     * 给你两个 非递增 的整数数组 nums1 和 nums2 ，数组下标均 从 0 开始 计数。
     * 下标对 (i, j) 中 0 <= i < nums1.length 且 0 <= j < nums2.length 。
     * 如果该下标对同时满足 i <= j 且 nums1[i] <= nums2[j] ，则称之为 有效 下标对，该下标对的 距离 为 j - i。
     * 返回所有 有效 下标对 (i, j) 中的 最大距离 。如果不存在有效下标对，返回 0 。
     * 一个数组 arr ，如果每个 1 <= i < arr.length 均有 arr[i-1] >= arr[i] 成立，那么该数组是一个 非递增 数组。
     */
    public static int maxDistance(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int L = 0;
        int R = 0;
        while (L < len1 && R < len2) {
            if (nums1[L] > nums2[R]) {
                L++;
            }
            R++;
        }
        return R - L - 1 >= 0 ? R - L - 1 : 0;
    }



}
